extends Node

class_name canWalk

func getRoutPlan(mapSpend:Dictionary, cantMove:ArraySet, reachPoints:ArrayList, initPoint:Point, initSteps:int, walkStepRout:HashMap, maxX, maxY):
#	print("获取路线规划。点：(", initPoint.x, ",", initPoint.y, ")", initSteps)
	if walkStepRout == null:
		walkStepRout = HashMap.new()
		var initStepRout = StepRout.new()
		var initRout:ArraySet = ArraySet.new()
		initRout.add(initPoint)
		initStepRout.init(initPoint, initSteps, initRout)
		walkStepRout.put(initPoint, initStepRout)
		
	while !reachPoints.isEmpty():
		var curPoint = reachPoints.get(0)
		reachPoints.remove(0)
#		print("check point, x=",curPoint.x,",y=",curPoint.y)
		## 判断当前是否可以剪枝
		var curStepRout:StepRout = walkStepRout.get(curPoint)
		var steps:int = curStepRout.steps
		var canCut = checkCanCut(curPoint, steps, walkStepRout)
#		print("判断当前节点：(", curPoint.x, ",", curPoint.y,"), 步数：", steps, ". canCut:", canCut)
		if !checkCanCut(curPoint, steps, walkStepRout):
			## 左
			if curPoint.x>0:
				var targetX = curPoint.x -1
				var targetY = curPoint.y
				var targetPoint = Point.new()
				if !cantMove.contains(targetPoint):
					targetPoint.init(targetX, targetY)
					var result:Dictionary = getBestNextStepRout(mapSpend, curPoint, targetPoint, steps, walkStepRout)
					if result.get("result"):
						reachPoints.add(targetPoint)
						walkStepRout = result.get("walkStepRout")
						var w = walkStepRout.get(targetPoint)
	#					print("新的可达点：x=",targetX,",y=",targetY,"。剩余步数：", w.steps)
					
			## 右
			if curPoint.x <maxX-1:
				var targetX = curPoint.x +1
				var targetY = curPoint.y
				var targetPoint = Point.new()
				targetPoint.init(targetX, targetY)
				if !cantMove.contains(targetPoint):
					var result:Dictionary = getBestNextStepRout(mapSpend, curPoint, targetPoint, steps, walkStepRout)
					if result.get("result"):
						reachPoints.add(targetPoint)
						walkStepRout = result.get("walkStepRout")
						var w = walkStepRout.get(targetPoint)
	#					print("新的可达点：x=",targetX,",y=",targetY,"。剩余步数：", w.steps)
		#				walkStepRout = getRoutPlan(mapSpend, targetPoint, steps-mapSpend[targetX][targetY], result.get("walkStepRout"))
					
			## 上
			if curPoint.y > 0:
				var targetX = curPoint.x
				var targetY = curPoint.y - 1
				var targetPoint = Point.new()
				targetPoint.init(targetX, targetY)
				if !cantMove.contains(targetPoint):
					var result:Dictionary = getBestNextStepRout(mapSpend, curPoint, targetPoint, steps, walkStepRout)
					if result.get("result"):
						reachPoints.add(targetPoint)
						walkStepRout = result.get("walkStepRout")
						var w = walkStepRout.get(targetPoint)
	#					print("新的可达点：x=",targetX,",y=",targetY,"。剩余步数：", w.steps)
		#				walkStepRout = getRoutPlan(mapSpend, targetPoint, steps-mapSpend[targetX][targetY], result.get("walkStepRout"))
					
			## 下
			if curPoint.y < maxY:
				var targetX = curPoint.x
				var targetY = curPoint.y + 1
				var targetPoint = Point.new()
				targetPoint.init(targetX, targetY)
				if !cantMove.contains(targetPoint):
					var result:Dictionary = getBestNextStepRout(mapSpend, curPoint, targetPoint, steps, walkStepRout)
					if result.get("result"):
						reachPoints.add(targetPoint)
						walkStepRout = result.get("walkStepRout")
						var w = walkStepRout.get(targetPoint)
	#					print("新的可达点：x=",targetX,",y=",targetY,"。剩余步数：", w.steps)
		#				walkStepRout = getRoutPlan(mapSpend, targetPoint, steps-mapSpend[targetX][targetY], result.get("walkStepRout"))
#			getRoutPlan(mapSpend, reachPoints, initPoint, curStepRout.steps, walkStepRout)
#	walkStepRout.remove(initPoint)
	return walkStepRout
	
func getBestNextStepRout(mapSpend:Dictionary, initPoint:Point, targetPoint:Point, steps:int, walkStepRout:HashMap)->Dictionary:
#	print("验证从点：(", initPoint.x, ",", initPoint.y, ") -> (", targetPoint.x, ",", targetPoint.y)
	var remainStep = steps - mapSpend[Vector2(targetPoint.x, targetPoint.y)]
	if remainStep < 0:
#		print("剪枝")
		return {"result":false, "walkStepRout":walkStepRout}
	if walkStepRout.contains(targetPoint):
		var sr:StepRout = walkStepRout.get(targetPoint)
		if sr.steps > remainStep:
#			print("剪枝")
			return {"result":false, "walkStepRout":walkStepRout}
			
	var initSR:StepRout = walkStepRout.get(initPoint)
	var initRout:ArraySet = initSR.rout
	var targetSR = StepRout.new()
	var targetRout = ArraySet.new()
	targetRout.copy(initRout)
	targetRout.add(targetPoint)
	targetSR.init(targetPoint, remainStep, targetRout)
	walkStepRout.put(targetPoint, targetSR)
#	print("可以走。步长:", targetRout.size(), "剩余步数：", remainStep)
#	printwalkStepRout(walkStepRout)
	return {"result":true, "walkStepRout":walkStepRout}

func checkCanCut(curPoint:Point, steps:int, walkStepRout:HashMap):
	var stepRout = walkStepRout.get(curPoint)
	if (stepRout.rout.contains(curPoint)):
		return false
	return  stepRout.steps < steps
	
func printwalkStepRout(walkStepRout:HashMap):
	var keys = walkStepRout.keys()
	print("**********")
	for o in keys.toArray():
		var sr:StepRout = walkStepRout.get(o)
		var p = sr.point
		var rout = sr.rout
		print("到达点：(", p.x, ",", p.y,"剩余步数：",sr.steps)
		var l = rout.toArray()
		for i in range(l.size()):
			var r = l[i]
			print(i,"：(",r.x,",",r.y,")")
	print("**********")
